/**
 * @param {character[][]} grid
 * @return {number}
 */
// 深度优先遍历
var numIslands = function (grid) {
    let points = []
    let m = grid.length, n = grid[0].length
    const directions = [{ x: 0, y: 1 }, { x: 0, y: -1 }, { x: 1, y: 0 }, { x: -1, y: 0 }]
    const visited = new Array(m).fill().map(() => {
        return new Array(n).fill(false)
    })
    function isValid(x, y) {
        if (x >= 0 && x < m && y >= 0 && y < n && nums[x][y] === '1' && !visited[x][y]) return true
    }
    // 这一步可以不用，在深度优先遍历的时候处理就好，如下面的方法
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == '1') points.push([i, j])
        }
    }
    const dfs = (x, y) => {
        visited[x][y] = true
        for (let i = 0; i < 4; i++) {
            let x1 = x + directions[i].x
            let y1 = y + directions[i].y
            if (isValid(x1, y1)) dfs(x1, y1)
        }
    }
    let ans = 0
    for (let i = 0; i < points.length; i++) {
        if (!visited[points[0]][points[1]]) {
            ans++
            dfs(points[0], points[1])
        }
    }
    return ans
};
/**
 * @param {character[][]} grid
 * @return {number}
 */
// 深度优先遍历
var numIslands = function (grid) {
    const row = grid.length;
    const column = grid[0].length
    const directions = [{ x: -1, y: 0 }, { x: 1, y: 0 }, { x: 0, y: -1 }, { x: 0, y: 1 }]
    const haveVisited = new Array(row).fill().map(() => {
        return new Array(column).fill(false)
    })
    const dfs = (i, j) => {
        haveVisited[i][j] = true
        for (let k = 0; k < 4; k++) {
            let xAxis = i + directions[k].x
            let yAxix = j + directions[k].y
            if (xAxis >= 0 && xAxis < row && yAxix >= 0 && yAxix < column && grid[xAxis][yAxix] === '1' && !haveVisited[xAxis][yAxix]) {
                dfs(xAxis, yAxix)
            }
        }
    }
    let ans = 0
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < column; j++) {
            if (!haveVisited[i][j] && grid[i][j] == '1') {
                dfs(i, j)
                ans++
            }
        }
    }
    return ans
};